package com.cqs.leetcode.recursion;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/8/16
 */
public class PermutationIILCCI {

    public String[] permutation(String S) {
        List<String> list = new ArrayList<>();
        char[] chars = S.toCharArray();
        Arrays.sort(chars);
        permutation(chars, new byte[S.length()], new char[S.length()], 0, list);
        String[] arr = new String[list.size()];
        list.toArray(arr);
        return arr;
    }

    private void permutation(char[] chars, byte[] used, char[] tmp, int level, List<String> result) {
        //finish condition
        if (level == chars.length) {
            result.add(new String(tmp));
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (used[i] == 1) {
                continue;
            }
            tmp[level] = chars[i];
            used[i] = 1;
            permutation(chars, used, tmp, level + 1, result);
            used[i] = 0;
            //重复的元素
            while ( (i+1) < chars.length && chars[i + 1] == chars[i] ) {
                i++;
            }
        }
    }

    public static void main(String[] args) {

        List<String> tests = Lists.newArrayList("aab","qwedredsw");
        for (String test : tests) {
            PermutationIILCCI lcci = new PermutationIILCCI();
            String[] permutation = lcci.permutation(test);
            System.out.println(test + "\t" + Lists.newArrayList(permutation));
        }

    }

}
